#include <stdio.h>
/* 2011年42题
 * 算法基本思想
 * 分别求出序列A和B的中位数，设a和b，求序列A和B的中位数过程如下
 *（1）若a=b，则a或b极为所求中位数，算法结束
 *（2）若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等
 *（3）若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等
 * 在保留的两个升序序列中，重复过程（1）（2）（3），直到两个序列中均只含一个元素为止，较小者即为所求的中位数
 * */
//int *A,int *B,int len
int MinSearch(int A[],int B[],int len)
{
    //分别表示序列A和B的首位数，末尾数和中位数，s是start的简写，d是end的简写
    int s1=0,d1=len-1,m1,s2=0,d2=len-1,m2;
    //循环判断结束条件是，两个数组均不断删除最后均只能剩下一个元素
    while (s1!=d1||s2!=d2)
    {
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(A[m1]==B[m2])
        {
            return A[m1];  //满足条件（1）
        }
        else if(A[m1]<B[m2])  //满足条件（2）
        {
            if((s1+d1)%2==0) //若元素个数为奇数，这里注意数组下标从0开始
            {
                s1=m1; //舍弃A中间点以前的部分且保留中间点
                d2=m2; //舍弃B中间点以后的部分且保留中间点
            } else{ //元素个数为偶数
                s1=m1+1; //舍弃A中间点以及中间点以前的部分
                d2=m2;   //舍弃B中间点以后的部分且保留中间点
            }
        }
        else  //满足条件（3），下面的操作和上面条件2是完全对称的
        {
            if((s1+d1)%2==0) //若元素个数为奇数，这里注意数组下标从0开始
            {
                d1=m1; //舍弃A中间点以后的部分且保留中间点
                s2=m2; //舍弃B中间点以前的部分且保留中间点
            } else{ //元素个数为偶数
                d1=m1; //舍弃A中间点以后的部分且保留中间点
                s2=m2+1; //舍弃B中间点以及中间点以前的部分
            }
        }
    }
}
int main() {
    int A[]={11,13,15,17,19};
    int B[]={2,4,6,8,20};
    int mid=MinSearch(A,B,5);
    printf("mid=%d\n",mid)
    return 0;
}
